
#include <iostream>
using namespace std;

/**
    堆排序：
        1首先对整个数组[n]实现一个大顶堆
        2然后将堆顶(第一个元素)和堆底(最后一个元素)交换，
        3然后对【0.n-1】这个数组执行1，2，重复


    堆的特点:
        a[0] >=a[1] && a[0]>=a[2]
        a[1] >=a[3] && a[1]>=a[4]
        .....
        即 a[i]>=a[2i+1] && a[i]>=a[2i+2]

*/
void swap_num(int arr[],int x,int y)
{
    int tmp = arr[x];
    arr[x] = arr[y];
    arr[y] = tmp;
}
void adjust(int arr[],int i,int n) //i为父节点，n为数组长度
{
    int parent = i;
    int child = 0;

    while(parent>=0)
    {
        child = 2*parent+1;
        //找到子节点更大的那个
        if(arr[child]<arr[child+1] && (child+1)<n)
        {
            child++;
        }
        //判断父节点和大的子节点，如果子节点大，则交换父节点和大子节点
        if(arr[parent]<arr[child])
        {
            swap_num(arr,parent,child);
        }
        parent--;
    }

}

void heapSort(int arr[],int n)
{
    int size_arr = n;
    for(int i = n/2-1;i>=0;i--)
    {
        adjust(arr,i,size_arr--);
        //交换首尾
        swap_num(arr,0,size_arr);

    }
}
int main()
{

    int arr[10] = {5,2,12,6,9,0,3,6,15,20};
    heapSort(arr,10);
    for(int i = 0;i<10;i++)
    {
        cout<<arr[i]<<",";
    }
    system("pause");
    return 0;
}
